#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>

#include "sudoku.h"

using namespace std;

void Move::print() const
{
  cout << x_ << " " << y_ << " " << number_ << endl;
}

void Puzzle::CreateStructure(const vector<int> &mypuzzle)
{
  rank_ = sqrt(mypuzzle.size());
  for(int i = 0; i < mypuzzle.size(); ++i)
  { 
    if(sudoku_.size() == 0 || sudoku_.back().size() % rank_ == 0)
    {
      sudoku_.push_back(vector<int>()); 
    }
    sudoku_.back().push_back(mypuzzle[i]);
  }
  print();
  cout << endl;
}

void Puzzle::print() const 
{
  for(int i = 0; i < rank_ ; ++i)
  {
    for(int j = 0; j < rank_; ++j)
    {
      cout << sudoku_[i][j] << " ";
    }
    cout << endl;
  }
}

void Puzzle::ReadMovesFromFile(){
  ifstream movefile("move.txt");
  if(!movefile.is_open())
  {
    cout <<"The move file can not open" << endl;
    return;
  }

  string line;
  int count;
  int x = -1;
  int y = -1;
  int number = -1;
  while(movefile.good())
  {
    getline(movefile, line);
    if(!movefile.good())
      return;

    count = sscanf(line.c_str(), "%d %d %d", &x, &y, &number);
    if(count < 3)
    {
      cout << "The given number is not right "
        << x << " "
        << y << " "
        << number << endl;
      continue;
    }
    Move move(x, y, number);
    move.print();
    if(CheckMoveNumbers(move))
    {
      sudoku_[x][y] = number;
    }
  }
}

bool Puzzle::CheckMoveNumbers(const Move &move) const{
  //avaiable number checking
  if(move.x() < 0 || move.x() >= rank_ ||
     move.y() < 0 || move.y() >= rank_ ||
     move.number() <= 0 || move.number() > rank_)
  {
    //cout << "The given number is out of the possible one " 
    //  << move.x() << " " 
    //  << move.y() << " "
    //  << move.number() << endl;
    return false;
  }

  //line and row checking
  for(int i = 0; i < rank_; ++i)
  {
    if(sudoku_[move.x()][i] == move.number() ||
       sudoku_[i][move.y()] == move.number())
    {
      //cout << "The same line or row has this number" << endl;
      return false;
    }
  }
  //cube checking
  int cube_rank = sqrt(rank_);
  int cube_x = move.x() / cube_rank * cube_rank ;
  int cube_y = move.y() / cube_rank * cube_rank ;
 
  for(int i = cube_x; i < cube_x + cube_rank; ++i)
  {
    for(int j = cube_y; j < cube_y + cube_rank; ++j)
    {
      if(sudoku_[i][j] == move.number())
      {
        //cout << "On the same cube has this number" << endl;
        return false;
      }
    }
  } 

  //cout << "Pass all checking" << endl;  
  return true;
}

bool Puzzle::ChoosePosition(int *x, int *y) const
{
  int count_empty = 0;
  *y = -1;
  for(int i = 0; i < rank_; i++)
  {
    for(int j = 0; j < rank_; j++)
    {
      if(sudoku_[i][j] != 0)
      {
        count_empty++;
      }
    }
  }
  
  if(count_empty == rank_ * rank_)
    return false;


  int count_max = -1;

  for(int i = 0; i < rank_; i++)
  {
    int count_line = 0;
    for(int j = 0; j < rank_; j++)
    {
      if(sudoku_[i][j] != 0)
      { 
        count_line++;
      }
    }
    if(count_line > count_max && count_line < rank_)
    {
      count_max = count_line;
      *x = i;
    }   
  }

  for(int i = 0; i < rank_; i++)
  {
    int count_line = 0;
    for(int j = 0; j < rank_; j++)
    {
      if(sudoku_[j][i] != 0)
      { 
        count_line++;
      }
    }
    if(count_line > count_max && count_line < rank_)
    {
      count_max = count_line;
      *y = i;
    }   
  }
  bool square_is_best = false;
  for(int square_i = 0; square_i < rank_; square_i += sqrt(rank_))
  {
    for(int square_j = 0; square_j < rank_; square_j += sqrt(rank_))
    {
      int count_square = 0;
      for(int i = square_i; i < square_i + sqrt(rank_); ++i)
      {
        for(int j = square_j; j < square_j + sqrt(rank_); ++j)
        {
          if(sudoku_[i][j] != 0)
            count_square++;
        }
      }
      if(count_square > count_max && count_square < rank_)
      {
        count_max = count_square;
        *x = square_i;
        *y = square_j;
        square_is_best = true;
      }
    } 
  }

  if(!square_is_best)
  {
    for(int j = 0; j < rank_; j++)
    {
      if (*y == -1)
      {
        if(sudoku_[*x][j] == 0)
        {
          *y = j;
          return true;
        }
      }
      else
      {
        if(sudoku_[j][*y] == 0)
        {
          *x = j;
          return true;
        }
      
      }
    }
  }
  else
  {
    for(int i = *x; i < *x + sqrt(rank_); ++i)
    {
      for(int j = *y; j < *y + sqrt(rank_); ++j)
      {
        if(sudoku_[i][j] == 0)
        {
          *x = i;
          *y = j;
          return true;
        }
      }
    }
  }
  
  *x = -1;
  return false;
}

bool Puzzle::ChoosePositionNaive(int *x, int *y) const
{
  for(int i = 0; i < rank_; i++)
  {
    for(int j = 0; j < rank_; j++)
    {
      if(sudoku_[i][j] == 0)
      {
        *x = i;
        *y = j; 
        return true;
      }
    }
  }
  return false;
}

bool Puzzle::SolvePuzzle()
{
  tries_++;
  int x = 0;
  int y = 0;
  if(!ChoosePosition(&x, &y))
  {
    if(x == -1)
    {
      cout << "Fatal error. No valid position found" << endl;
      return true;
    }
    cout << "Puzzle solved with " << tries_ << " moves!" << endl;
    print();
    return true;
  }
  
  for(int number = 1; number <= rank_; number++)
  {
    Move move(x, y, number);
    if(CheckMoveNumbers(move))
    {
      sudoku_[x][y] = number;
      if(SolvePuzzle())
      {
        return true;
      }
    }
  }
  sudoku_[x][y] = 0;
  return false;
}

int main(int argc, char *argv[]){
  //open and read the file
  Puzzle puz;
  int temp_number;
  vector<int> mypuzzle;
  ifstream puzzlefile ("puzzle.txt");
  if(!puzzlefile.is_open())
  {
    cout << "The puzzle file can not open" << endl;
    return 0;
  }
  else
  {
    while(puzzlefile >> temp_number)
    {
      mypuzzle.push_back(temp_number);  
    }
    double d_rank = sqrt(mypuzzle.size());
    int i_rank = d_rank;
    if(i_rank != d_rank)
    {
      cout << "The puzzle size is wrong " << endl; 
    }
    else
    {
      cout << "The puzzle size is " << i_rank << endl;
    }
  }
  puzzlefile.close();
  
  //puzzle structure creation
  
  puz.CreateStructure(mypuzzle);
  //puz.ReadMovesFromFile();
  puz.SolvePuzzle();
  return 0;
}
